Relationship between Conditional Diagnosability and 2-extra Connectivity of Symmetric Graphs

摘要

The conditional diagnosability and the 2-extra connectivity are two importantparameters to measure ability of diagnosing faulty processors andfault-tolerance in a multiprocessor system. The conditional diagnosability$t_c(G)$ of $G$ is the maximum number $t$ for which $G$ is conditionally$t$-diagnosable under the comparison model, while the 2-extra connectivity$\kappa_2(G)$ of a graph $G$ is the minimum number $k$ for which there is avertex-cut $F$ with $|F|=k$ such that every component of $G-F$ has at least $3$vertices. A quite natural problem is what is the relationship between themaximum and the minimum problem? This paper partially answer this problem byproving $t_c(G)=\kappa_2(G)$ for a regular graph $G$ with some acceptableconditions. As applications, the conditional diagnosability and the 2-extraconnectivity are determined for some well-known classes of vertex-transitivegraphs, including, star graphs, $(n,k)$-star graphs, alternating groupnetworks, $(n,k)$-arrangement graphs, alternating group graphs, Cayley graphsobtained from transposition generating trees, bubble-sort graphs, $k$-ary$n$-cube networks and dual-cubes. Furthermore, many known results about thesenetworks are obtained directly.